#include <set>
#include <unordered_map>

using namespace std;

/**
 * @brief 460. LFU 缓存
 * https://leetcode.cn/problems/lfu-cache/
 * 通过 set 红黑树对 Item 进行排序
 */
class LFUCache {
public:
    LFUCache(int capacity) : capa(capacity) {}

    int get(int key) {
        if (!cache.count(key)) return -1;
        Node* node = cache[key];
        updateNodeStatus(node);
        return node->value;
    }

    void put(int key, int value) {
        if (cache.count(key)) {
            Node* node = cache[key];
            node->value = value;
            updateNodeStatus(node);
            return;
        }
        Node* node = new Node(key, value, ++time);
        size += 1;
        if (size > capa) {
            size -= 1;
            cache.erase((*nodes.begin())->key);
            nodes.erase(nodes.begin());
        }
        nodes.insert(node);
        cache[key] = node;
    }

private:
    struct Node {
        int key, value;
        int freq, time;
        Node(int key, int value, int time) : key(key), value(value), freq(1), time(time) {}

        // 用于比较 Node，适用于 set<Node>
        bool operator<(const Node& other) const {
            if (freq == other.freq) return time < other.time;
            return freq < other.freq;
        }

        // 用于比较 Node 指针，适用于 set<Node*>
        // 注意 set 类模板要传入比较器 set<Node*, Node::Comp>
        struct Comp {
            bool operator()(const Node* l, const Node* r) const {
                return *l < *r;
            }
        };
    };

    int size = 0;
    int capa = 0;
    int time = 0;
    set<Node*, Node::Comp> nodes;
    unordered_map<int, Node*> cache;

    // 要手动移除再插入，不会自动更改排序
    void updateNodeStatus(Node* node) {
        nodes.erase(node);
        node->freq += 1;
        node->time = ++time;
        nodes.insert(node);
    }
};

/**
 * Your LFUCache object will be instantiated and called as such:
 * LFUCache* obj = new LFUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */
